 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> num_set;
        //对原数组去重
        for (auto& num : nums)
            num_set.insert(num);

        int longest = 0;
        for (auto& num : num_set)
        {
            //如果当前数的前一个数不存在,则直接重新开始计数
            if (!num_set.count(num - 1))
            {
                int curNum = num;
                int cur = 1;

                //因为前面没有连续的数，所以从后面开始找连续的数，直到找到没有连续数为止
                while (num_set.count(curNum + 1))
                {
                    curNum += 1;
                    cur += 1;
                }
                //出去之后直接与最大值进行比较
                longest = max(longest, cur);
            }
        }

        return longest;
    }
};

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end)
    {
        while (start < end)
            swap(nums[start++], nums[end--]);
    }
    void rotate(vector<int>& nums, int k) {
        // int n = nums.size();

        // vector<int> newNums(n);
        // for(int i = 0; i < n; i++)
        // {
        //     newNums[(i + k) % n] = nums[i];
        // }

        // nums.assign(newNums.begin(), newNums.end);

        k %= nums.size();

        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getLength(ListNode* head)
    {
        int cnt = 0;
        while (head)
        {
            head = head->next;
            cnt++;
        }
        return cnt;
    }
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        // //特殊情况
        // if(headA == nullptr || headB == nullptr) return nullptr;

        // ListNode* curA = headA, *curB = headB;
        // while(curA != curB)
        // {
        //     curA = curA == nullptr ? headB : curA->next;
        //     curB = curB == nullptr ? headA : curB->next;
        // }

        // return curA;

        //先获取两个链表的长度
        int lenA = getLength(headA);
        int lenB = getLength(headB);

        //比较两个链表的长度，让长的链表先走到和短的链表相同的位置，如果两个链表一样长，则不进行处理
        int len = 0;
        if (lenA > lenB)
        {
            len = lenB;
            while (lenA-- > lenB)
                headA = headA->next;
        }
        else
        {
            len = lenA;
            while (lenA < lenB--)
                headB = headB->next;
        }

        //此时走两个链表中短链表的长度即可，如果遇到了，则说明有交点，否则没有
        while (len--)
        {
            if (headA == headB) return headA;
            headA = headA->next;
            headB = headB->next;
        }

        //走到这里说明没有交点
        return nullptr;
    }
};